UVa/12323 - Inspecting Radars/12323.2.cpp

   1 // Accepted
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <deque>
  19 #include <stack>
  20 #include <list>
  21 #include <map>
  22 #include <set>
  23
  24 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  26 #define D(x) cout << #x " is " << x << endl
  27
  28 typedef pair<int, int> point;
  29
  30 const int MAXN = 10000;
  31 const int MAXR = 101;
  32 const int MAXW = 720;
  33
  34 int mat[MAXR][MAXW];
  35 int sum[MAXR][MAXW];
  36
  37 void precompute() {
  38     for (int i = 0; i < MAXR; ++i) {
  39         for (int j = 0; j < MAXW; ++j) {
  40             sum[i][j] = mat[i][j];
  41             if (i > 0) sum[i][j] += sum[i-1][j];
  42             if (j > 0) sum[i][j] += sum[i][j-1];
  43             if (i > 0 and j > 0) sum[i][j] -= sum[i-1][j-1];
  44         }
  45     }
  46 }
  47
  48 int rectangle(int r1, int c1,   int r2, int c2) {
  49     int ans = sum[r2][c2];
  50     if (r1 > 0) ans -= sum[r1-1][c2];
  51     if (c1 > 0) ans -= sum[r2][c1-1];
  52     if (r1 > 0 and c1 > 0) ans += sum[r1-1][c1-1];
  53     return ans;
  54 }
  55
  56 void solve(int height, int width) {
  57     int ans = 0;
  58     for (int i = 0; i + height < MAXR; ++i) {
  59         for (int j = 0; j + width < MAXW; ++j) {
  60             int option = rectangle(i, j,     i + height, j + width);
  61             if (option > ans) ans = option;
  62         }
  63     }
  64     printf("%d\n", ans);
  65 }
  66
  67 int main(){
  68     int N, R;
  69     while (scanf("%d %d", &N, &R) == 2) {
  70         if (N == 0 and R == 0) break;
  71         memset(mat, 0, sizeof mat);
  72
  73         for (int i = 0; i < N; ++i) {
  74             int distance, angle;
  75             scanf("%d %d", &distance, &angle);
  76             mat[distance][angle]++;
  77             mat[distance][angle + 360]++;
  78         }
  79         precompute();
  80
  81         int E;
  82         scanf("%d", &E);
  83         while (E--) {
  84             int distance, angle;
  85             scanf("%d %d", &distance, &angle);
  86             solve(distance - 1, angle);
  87         }
  88     }
  89     return 0;
  90 }